package leetcode.动态规划.simple;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2022/1/9 下午9:32
 */
public class _118杨辉三角2 {
    /*
        给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
     */
    public static List<Integer> getRow(int rowIndex) {
        List<Integer> l1 = new LinkedList<>();
        if (rowIndex == 0) {
            l1.add(1);
            return l1;
        }
        if (rowIndex == 1) {
            l1.add(1);
            l1.add(1);
            return l1;
        }
        List<Integer> pre = new ArrayList<>();
        pre.add(1);
        pre.add(1);

        int row = rowIndex + 1;

        for (int line = 3; line <= row; line++) {
            int last = 1;
            for (int i = 0; i < line; i++) {
                if (i == 0 || i == line - 1) {
                    if (i == line - 1) {
                        pre.add(1);
                    } else {
                        pre.set(i, 1);
                    }
                } else {
                    int tempLast = last;
                    // 正常应该是 pre.set(i,pre.get(i-1)+pre.get(i))
                    //但当去掉首尾的1后，中间有超过1个的数据时，假如是第4行，一共有4个数据，
                    //更新完第1个后(从0计数)，第1个数变成了pre(1)= pre(0)+pre(1)=1+2=3，
                    //在更新第2个数时 pre(2)=pre(1)+pre(2)，正常应该是2+1=3，但是因为更新第1个数时把 pre(1)覆盖为了3,最终就变成了pre(2)=3+1=4，为了避免被覆盖，使用 last 记录更新 i 前的 pre(i)，作为下次的 pre(i-1)使用
                    last = pre.get(i);
                    pre.set(i, tempLast + pre.get(i));
                }
            }
        }
        return pre;
    }

    public static void main(String[] args) {
        List<Integer> row = getRow(3);
        System.out.println(row);
    }

}
